package leetcode_800;

/**
 *@author 周杨
 *LargestPlusSign_764 题目没有看懂 反正是动态规划
 *describe:用动态规划 AC 23%
 *2018年10月18日 下午2:34:18
 */
public class LargestPlusSign_764 {
	public int orderOfLargestPlusSign(int N, int[][] mines) {
		int[][][] grid = new int[N][N][4];
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				for (int k = 0; k < 4; ++k) {
					grid[i][j][k] = 1;
				}
			}
		}

		for (int[] mine : mines) {
			int r = mine[0];
			int c = mine[1];
			for (int k = 0; k < 4; ++k)
				grid[r][c][k] = 0;
		}

		for (int i = 0; i < N; ++i) {
			for (int j = 1; j < N; ++j) {
				if (grid[i][j][0] == 1)
					grid[i][j][0] += grid[i][j - 1][0];
			}
			for (int j = N - 2; j >= 0; --j) {
				if (grid[i][j][1] == 1)
					grid[i][j][1] += grid[i][j + 1][1];
			}
		}

		for (int j = 0; j < N; ++j) {
			for (int i = 1; i < N; ++i) {
				if (grid[i][j][2] == 1)
					grid[i][j][2] += grid[i - 1][j][2];
			}
			for (int i = N - 2; i >= 0; --i) {
				if (grid[i][j][3] == 1)
					grid[i][j][3] += grid[i + 1][j][3];
			}
		}

		int ans = 0;
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				int order = Math.min(Math.min(grid[i][j][0], grid[i][j][1]), Math.min(grid[i][j][2], grid[i][j][3]));
				ans = Math.max(ans, order);
			}
		}
		return ans;
	}
}
